package com.leetcode.算法策略相关.递归;

/**
 * @author: ZhouBert
 * @date: 2021/3/3
 * @description: 70. 爬楼梯
 * https://leetcode-cn.com/problems/climbing-stairs/
 */
public class A_70_爬楼梯 {


	static A_70_爬楼梯 action = new A_70_爬楼梯();

	public static void main(String[] args) {
		test1();
	}

	public static void test1() {
		int n = 3;
		int res = action.climbStairs(n);
		System.out.println("res = " + res);
	}

	int[] res;

	/**
	 * 这道题跟 {@link A_1137_第N个泰波那契数} 惊人相似
	 * 建模：
	 * res[n] = res[n-1] + res[n-2]
	 *
	 * @param n
	 * @return
	 */
	public int climbStairs(int n) {
		if (n==1){
			return 1;
		}
		res = new int[n + 1];
		res[1] = 1;
		res[2] = 2;
		if (n < 3) {
			return res[n];
		}
		climbByRecursive(n);
		return res[n];
	}

	/**
	 * 将递归的结果写入数组
	 *
	 * @param n
	 */
	private void climbByRecursive(int n) {
		if (res[n - 2] == 0) {
			climbByRecursive(n - 2);
		}
		if (res[n - 1] == 0) {
			climbByRecursive(n - 1);
		}
		res[n] = res[n - 1] + res[n - 2];
	}
}
